package com.zjsru.plan2024.oneday;

import com.zjsru.common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 从中序与后序遍历序列构造二叉树
 * @Author: cookLee
 * @Date: 2024-02-21
 */
public class BuildTree {

    /**
     * 主
     * \
     * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
     * 输出：[3,9,20,null,null,15,7]
     * \
     * @param args args
     */
    public static void main(String[] args) {
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        int[] postorder = new int[]{9, 15, 7, 20, 3};
        BuildTree buildTree = new BuildTree();
        System.out.println(buildTree.buildTree(inorder, postorder));
    }

    /**
     * 后置定位
     */
    int postIdx;
    /**
     * 后置树数组
     */
    int[] postorder;
    /**
     * 中序排序数组
     */
    int[] inorder;
    /**
     * 树形图
     */
    Map<Integer, Integer> treeMap = new HashMap<Integer, Integer>();

    /**
     * 递归
     * @param inorder   inorder
     * @param postorder 后者
     * @return {@link TreeNode}
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //后序遍历定位，从最后一位开始
        postIdx = postorder.length - 1;
        this.inorder = inorder;
        this.postorder = postorder;

        //将数组放到哈希表中
        int idx = 0;
        for (Integer val : inorder) {
            treeMap.put(val, idx++);
        }

        return this.helper(0, inorder.length - 1);
    }

    /**
     * 递归助手类
     * @param left  左
     * @param right 右侧
     * @return {@link TreeNode}
     */
    private TreeNode helper(int left, int right) {
        if (left > right) {
            return null;
        }

        //postIdx下标位置的树为子树根节点
        int root = this.postorder[postIdx];
        TreeNode rootNode = new TreeNode(root);

        //因为map是按照中序遍历放入的，所以可以根据root的位置分为左右子树
        Integer index = this.treeMap.get(root);

        //下标减一
        this.postIdx--;

        //构造右子树
        rootNode.right = this.helper(index + 1, right);
        //构造左子树
        rootNode.left = this.helper(left, index - 1);

        return rootNode;
    }

}
